2169. Перестановки

По заданному натуральному числу n выведите все перестановки целых чисел от 1 до n в лексикографическом порядке.

Вход. Одно натуральное число n (1 ≤ n ≤ 8).

Выход. Выведите все перестановки чисел от 1 до n в лексикографическом порядке. Каждую перестановку следует выводить в отдельной строке.

Пример входа

Пример выхода

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

РЕШЕНИЕ

комбинаторика - перестановки

В задаче следует сгенерировать все перестановки чисел от 1 до n. Это можно сделать, например, при помощи функции next_permutation.

Реализация алгоритма

Массив m будем использовать для генерации перестановок.

int m[10];

Читаем входное значение n.

scanf("%d",&n);

Заполняем массив m начальной перестановкой 1 2 3 …. n, начиная с первого индекса.

for (i = 1; i <= n; i++)

m[i] = i;

С помощью функции next_permutation генерируем все перестановки – от лексикографически наименьшей до лексикографически наибольшей.

{

Каждую сгенерированную перестановку выводим в отдельной строке.

for (i = 1; i <= n; i++)

printf("%d ",m[i]);

printf("\n");

} while (next_permutation(m + 1, m + n + 1));

Реализация алгоритма – вектор

Вектор v будем использовать для генерации перестановок.

vector<int> v;

Читаем входное значение n.

scanf("%d", &n);

Заполняем массив v начальной перестановкой 1 2 3 …. n, начиная с нулевого индекса.

v.resize(n);

for (i = 0; i < n; i++)

v[i] = i + 1;

{

Выводим текущую перестановку в отдельной строке.

for (i = 0; i < n; i++)

printf("%d ", v[i]);

printf("\n");

} while (next_permutation(v.begin(), v.end()));